{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Most Similar Path in a Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mostSimilar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #图中最相似的路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们有&nbsp;<code>n</code>&nbsp;座城市和&nbsp;<code>m</code>&nbsp;条双向道路&nbsp;<code>roads</code>&nbsp;，其中&nbsp;<code>roads[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;连接城市&nbsp;<code>a<sub>i</sub></code>&nbsp;和城市&nbsp;<code>b<sub>i</sub></code>。每个城市的名称由字符串数组&nbsp;<code>names</code>&nbsp;中给出的三个大写英文字母组成。从任意城市&nbsp;<code>x</code>&nbsp;出发，你可以到达任意城市&nbsp;<code>y</code> ，其中&nbsp;<code>y != x</code>&nbsp;（即：城市和道路形成一张无向连通图）。</p>\n",
    "\n",
    "<p>给定一个字符串数组&nbsp;<code>targetPath</code>，你需要找出图中与&nbsp;<code>targetPath</code>&nbsp;的<strong> 长度相同</strong> 且<strong> 编辑距离</strong><strong>最小</strong> 的路径。</p>\n",
    "\n",
    "<p>你需要返回<em> </em><strong>编辑距离最小的路径中节点的顺序</strong><em> </em>。该路径应当与&nbsp;<code>targetPath</code>&nbsp;的长度相等，且路径需有效（即：&nbsp;<code>ans[i]</code>&nbsp;和&nbsp;<code>ans[i + 1]</code>&nbsp;间应存在直接连通的道路）。如果有多个答案，返回任意一个。</p>\n",
    "\n",
    "<p><strong>编辑距离</strong> 的定义如下：</p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2020/08/08/edit.jpg\" /></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/08/e1.jpg\" style=\"height: 300px; width: 213px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, roads = [[0,2],[0,3],[1,2],[1,3],[1,4],[2,4]], names = [\"ATL\",\"PEK\",\"LAX\",\"DXB\",\"HND\"], targetPath = [\"ATL\",\"DXB\",\"HND\",\"LAX\"]\n",
    "<strong>输出：</strong>[0,2,4,2]\n",
    "<strong>解释：</strong>[0,2,4,2], [0,3,0,2] 和 [0,3,1,2] 都是正确答案。\n",
    "[0,2,4,2] 等价于 [\"ATL\",\"LAX\",\"HND\",\"LAX\"] ，与 targetPath 的编辑距离 = 1。\n",
    "[0,3,0,2] 等价于 [\"ATL\",\"DXB\",\"ATL\",\"LAX\"] ，与 targetPath 的编辑距离 = 1。\n",
    "[0,3,1,2] 等价于 [\"ATL\",\"DXB\",\"PEK\",\"LAX\"] ，与 targetPath 的编辑距离 = 1。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/08/e2.jpg\" style=\"height: 200px; width: 200px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, roads = [[1,0],[2,0],[3,0],[2,1],[3,1],[3,2]], names = [\"ATL\",\"PEK\",\"LAX\",\"DXB\"], targetPath = [\"ABC\",\"DEF\",\"GHI\",\"JKL\",\"MNO\",\"PQR\",\"STU\",\"VWX\"]\n",
    "<strong>输出：</strong>[0,1,0,1,0,1,0,1]\n",
    "<strong>解释：</strong>任意路径与 targetPath 的编辑距离都等于 8。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/09/e3.jpg\" style=\"height: 106px; width: 600px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6, roads = [[0,1],[1,2],[2,3],[3,4],[4,5]], names = [\"ATL\",\"PEK\",\"LAX\",\"ATL\",\"DXB\",\"HND\"], targetPath = [\"ATL\",\"DXB\",\"HND\",\"DXB\",\"ATL\",\"LAX\",\"PEK\"]\n",
    "<strong>输出：</strong>[3,4,5,4,3,2,1]\n",
    "<strong>解释：</strong>[3,4,5,4,3,2,1] 是唯一与 targetPath 的编辑距离 = 0 的路径。\n",
    "该路径等价于 [\"ATL\",\"DXB\",\"HND\",\"DXB\",\"ATL\",\"LAX\",\"PEK\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>m == roads.length</code></li>\n",
    "\t<li><code>n - 1 &lt;= m &lt;= (n * (n - 1) / 2)</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub>&nbsp;</code></li>\n",
    "\t<li>给定的图保证是<strong>连通</strong>的，任意两个节点<strong>至多有一个</strong>直接连通的道路。</li>\n",
    "\t<li><code>names.length == n</code></li>\n",
    "\t<li><code>names[i].length == 3</code></li>\n",
    "\t<li><code>names[i]</code>&nbsp;包含大写英文字母。</li>\n",
    "\t<li>可能有两个名称<strong>相同</strong>的城市。</li>\n",
    "\t<li><code>1 &lt;= targetPath.length &lt;= 100</code></li>\n",
    "\t<li><code>targetPath[i].length == 3</code></li>\n",
    "\t<li><code>targetPath[i]</code> 由大写英文字母组成。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>如果路径中每个节点只可访问一次，你该如何修改你的答案？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-most-similar-path-in-a-graph](https://leetcode.cn/problems/the-most-similar-path-in-a-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-most-similar-path-in-a-graph](https://leetcode.cn/problems/the-most-similar-path-in-a-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[0,2],[0,3],[1,2],[1,3],[1,4],[2,4]]\\n[\"ATL\",\"PEK\",\"LAX\",\"DXB\",\"HND\"]\\n[\"ATL\",\"DXB\",\"HND\",\"LAX\"]', '4\\n[[1,0],[2,0],[3,0],[2,1],[3,1],[3,2]]\\n[\"ATL\",\"PEK\",\"LAX\",\"DXB\"]\\n[\"ABC\",\"DEF\",\"GHI\",\"JKL\",\"MNO\",\"PQR\",\"STU\",\"VWX\"]', '6\\n[[0,1],[1,2],[2,3],[3,4],[4,5]]\\n[\"ATL\",\"PEK\",\"LAX\",\"ATL\",\"DXB\",\"HND\"]\\n[\"ATL\",\"DXB\",\"HND\",\"DXB\",\"ATL\",\"LAX\",\"PEK\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:\n",
    "        d = {_:[] for _ in range(n)}\n",
    "        for road in roads:\n",
    "            d[road[0]].append(road[1])\n",
    "            d[road[1]].append(road[0])\n",
    "        maximum = 1000000\n",
    "        m = len(targetPath)\n",
    "        dp = [[maximum for _ in range(n)] for _ in range(m)]\n",
    "        marker = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            dp[0][j] = 0 if names[j] == targetPath[0] else 1\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                temp = 0 if names[j] == targetPath[i] else 1\n",
    "                cost = 0\n",
    "                for front in d[j]:\n",
    "                    cost = dp[i-1][front] + temp\n",
    "                    if cost > m:\n",
    "                        continue\n",
    "                    if cost < dp[i][j]:\n",
    "                        dp[i][j] = cost\n",
    "                        marker[i][j] = front\n",
    "        path = []\n",
    "        t = [(dp[m-1][_],_) for _ in range(n)]\n",
    "        t.sort()\n",
    "        while t:\n",
    "            c = t.pop(0)\n",
    "            j = c[1]\n",
    "            path = [j,]\n",
    "            temp = marker[m-1][j]\n",
    "            counter = m - 1\n",
    "            while counter and temp != -1:\n",
    "                path.append(temp)\n",
    "                j = marker[counter][j]\n",
    "                counter -= 1\n",
    "                temp = marker[counter][j]\n",
    "            if len(path) == m:\n",
    "                path.reverse()\n",
    "                return path\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:\n",
    "        d = {_:[] for _ in range(n)}\n",
    "        for road in roads:\n",
    "            d[road[0]].append(road[1])\n",
    "            d[road[1]].append(road[0])\n",
    "        maximum = 1000000\n",
    "        m = len(targetPath)\n",
    "        dp = [[maximum for _ in range(n)] for _ in range(m)]\n",
    "        marker = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            dp[0][j] = 0 if names[j] == targetPath[0] else 1\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                temp = 0 if names[j] == targetPath[i] else 1\n",
    "                cost = 0\n",
    "                for front in d[j]:\n",
    "                    cost = dp[i-1][front] + temp\n",
    "                    if cost > m:\n",
    "                        continue\n",
    "                    if cost < dp[i][j]:\n",
    "                        dp[i][j] = cost\n",
    "                        marker[i][j] = front\n",
    "        path = []\n",
    "        j = dp[m-1].index(min(dp[m-1]))\n",
    "        path = [j,]\n",
    "        temp = marker[m-1][j]\n",
    "        counter = m - 1\n",
    "        while counter:\n",
    "            path.append(temp)\n",
    "            j = marker[counter][j]\n",
    "            counter -= 1\n",
    "            temp = marker[counter][j]\n",
    "        if len(path) == m:\n",
    "            path.reverse()\n",
    "            return path\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:\n",
    "        d = {_:[] for _ in range(n)}\n",
    "        for road in roads:\n",
    "            d[road[0]].append(road[1])\n",
    "            d[road[1]].append(road[0])\n",
    "        maximum = 1000000\n",
    "        m = len(targetPath)\n",
    "        dp = [[maximum for _ in range(n)] for _ in range(m)]\n",
    "        marker = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            dp[0][j] = 0 if names[j] == targetPath[0] else 1\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                temp = 0 if names[j] == targetPath[i] else 1\n",
    "                cost = 0\n",
    "                for front in d[j]:\n",
    "                    cost = dp[i-1][front] + temp\n",
    "                    if cost > m:\n",
    "                        continue\n",
    "                    if cost < dp[i][j]:\n",
    "                        dp[i][j] = cost\n",
    "                        marker[i][j] = front\n",
    "        path = []\n",
    "        t = [(dp[m-1][_],_) for _ in range(n)]\n",
    "        t.sort()\n",
    "        while t:\n",
    "            c = t.pop(0)\n",
    "            j = c[1]\n",
    "            path = [j,]\n",
    "            temp = marker[m-1][j]\n",
    "            counter = m - 1\n",
    "            while counter:\n",
    "                path.append(temp)\n",
    "                j = marker[counter][j]\n",
    "                counter -= 1\n",
    "                temp = marker[counter][j]\n",
    "            if len(path) == m:\n",
    "                path.reverse()\n",
    "                return path\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:\n",
    "        g = defaultdict(list) \n",
    "        for a, b in roads:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        m = len(targetPath)\n",
    "        dp = [[float('inf')]*n for _ in range(m+1)]\n",
    "        f =  [[-1]*n for _ in range(m+1)]\n",
    "        for i in range(n):\n",
    "            dp[0][i] = 0 \n",
    "        for i in range(1, m+1):\n",
    "            for v in range(n):\n",
    "                for u in g[v]:\n",
    "                    if dp[i][v] > dp[i-1][u] + int(names[v] != targetPath[i-1]):\n",
    "                        dp[i][v] = dp[i-1][u] + int(names[v] != targetPath[i-1])\n",
    "                        f[i][v] = u \n",
    "        arr = []\n",
    "        p = 0 \n",
    "        for i in range(n):\n",
    "            if dp[m][p] > dp[m][i]:\n",
    "                p = i \n",
    "        arr.append(p)\n",
    "        for i in range(m-1, 0, -1):\n",
    "            p = f[i+1][p]\n",
    "            arr.append(p) \n",
    "        return arr[::-1] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in roads:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        m = len(targetPath)\n",
    "        f = [[inf] * n for _ in range(m)]\n",
    "        pre = [[-1] * n for _ in range(m)]\n",
    "        for j, s in enumerate(names):\n",
    "            f[0][j] = targetPath[0] != s\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                for k in g[j]:\n",
    "                    if (t := f[i - 1][k] + (targetPath[i] != names[j])) < f[i][j]:\n",
    "                        f[i][j] = t\n",
    "                        pre[i][j] = k\n",
    "        k = 0\n",
    "        mi = inf\n",
    "        for j in range(n):\n",
    "            if f[-1][j] < mi:\n",
    "                mi = f[-1][j]\n",
    "                k = j\n",
    "        ans = [0] * m\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            ans[i] = k\n",
    "            k = pre[i][k]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:\n",
    "        # 编辑距离最小 长度一样的\n",
    "        n = len(names)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in roads:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        @cache\n",
    "        def dfs(cur_index, pre_node):\n",
    "            if cur_index == len(targetPath):\n",
    "                return 0, []\n",
    "            mx_dis = inf\n",
    "            res = []\n",
    "            for nex in g[pre_node]:\n",
    "                cur_dis, cur_path = dfs(cur_index+1, nex)\n",
    "                cur_dis += 1 if names[nex] != targetPath[cur_index] else 0\n",
    "                if cur_dis < mx_dis:\n",
    "                    mx_dis = cur_dis\n",
    "                    res = [nex] + cur_path\n",
    "            return mx_dis, res\n",
    "\n",
    "        min_dis = inf\n",
    "        ans = []\n",
    "        for i in range(len(names)):\n",
    "            cur_dis, cur_path = dfs(0, i)\n",
    "            if cur_dis < min_dis:\n",
    "                min_dis = cur_dis\n",
    "                ans = cur_path\n",
    "        dfs.cache_clear()\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:\n",
    "        e=collections.defaultdict(list)\n",
    "        for a,b in roads:\n",
    "            e[a].append(b)\n",
    "            e[b].append(a)\n",
    "        m=len(targetPath)\n",
    "        @cache\n",
    "        def dfs(x,now):\n",
    "            if x>=m: \n",
    "                return 0,[]\n",
    "            cost=float(\"inf\")\n",
    "            path=[]\n",
    "            for i in e[now]:\n",
    "                c,p=dfs(x+1,i)\n",
    "                if c<cost:\n",
    "                    cost=c\n",
    "                    path=p\n",
    "            if names[now]!=targetPath[x]:\n",
    "                cost+=1\n",
    "            path=[now]+path\n",
    "            return cost,path\n",
    "        ans,ret=float(\"inf\"),[]\n",
    "        for i in range(n):\n",
    "            #print(i)\n",
    "            c,p=dfs(0,i)\n",
    "            if c<ans:\n",
    "                ans=c\n",
    "                ret=p\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:\n",
    "        e=collections.defaultdict(list)\n",
    "        for a,b in roads:\n",
    "            e[a].append(b)\n",
    "            e[b].append(a)\n",
    "        m=len(targetPath)\n",
    "        @cache\n",
    "        def dfs(x,now):\n",
    "            if x>=m: \n",
    "                return 0,[]\n",
    "            cost=float(\"inf\")\n",
    "            path=[]\n",
    "            for i in e[now]:\n",
    "                c,p=dfs(x+1,i)\n",
    "                if c<cost:\n",
    "                    cost=c\n",
    "                    path=p\n",
    "            if names[now]!=targetPath[x]:\n",
    "                cost+=1\n",
    "            path=[now]+path\n",
    "            return cost,path\n",
    "        ans,ret=float(\"inf\"),[]\n",
    "        for i in range(n):\n",
    "            #print(i)\n",
    "            c,p=dfs(0,i)\n",
    "            if c<ans:\n",
    "                ans=c\n",
    "                ret=p\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:\n",
    "        # 本质上是bottom-to-up的树形动态规划此处是无向图而已\n",
    "        dct = defaultdict(list)\n",
    "        for x, y in roads:\n",
    "            dct[x].append(y)\n",
    "            dct[y].append(x)\n",
    "\n",
    "\n",
    "        # 使用虚拟节点方便进行统一处理\n",
    "        dct[-1] = list(range(n))\n",
    "        m = len(targetPath)\n",
    "\n",
    "\n",
    "        # 从当前节点cur_node匹配targetPath[cur_index:]往后的最优代价\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur_node, cur_index):\n",
    "            # 对所有路径虚拟源点cur_node为-1的cur_dis是否加1都一样\n",
    "            if cur_index >= m:\n",
    "                return 0, []\n",
    "            cur_cost = int(names[cur_node] != targetPath[cur_index])\n",
    "            cur_dis = inf\n",
    "            nxt_index= cur_index + 1\n",
    "\n",
    "            # 遍历所有的下一步节点注意虚拟路径源点-1是单项输出的\n",
    "            for nxt_node in dct[cur_node]:\n",
    "                nxt_dis, nxt_path = dfs(nxt_node, nxt_index)\n",
    "                nxt_dis += cur_cost\n",
    "                if nxt_dis < cur_dis:\n",
    "                    cur_dis= nxt_dis\n",
    "                    cur_path = [cur_node] + nxt_path\n",
    "            return cur_dis, cur_path\n",
    "        return dfs(-1,-1)[1][1:]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:\n",
    "        \"\"\"\n",
    "        :param n:\n",
    "        :param roads:\n",
    "        :param names:\n",
    "        :param targetPath:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(list)\n",
    "        for i in roads:\n",
    "            m1[i[0]].append(i[1])\n",
    "            m1[i[1]].append(i[0])\n",
    "        m2 = {}\n",
    "        for k, v in enumerate(names):\n",
    "            m2[v] = k\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_ans(idx, cur_pos):\n",
    "            if idx == len(targetPath):\n",
    "                return [], 0\n",
    "            curv = names[cur_pos]\n",
    "            ans = []\n",
    "            anscnt = -1\n",
    "            if curv == targetPath[idx]:\n",
    "                for i in m1[cur_pos]:\n",
    "                    ret, cnt1 = get_ans(idx + 1, i)\n",
    "                    if cnt1 + 1 >= anscnt:\n",
    "                        anscnt = cnt1 + 1\n",
    "                        ans = [cur_pos] + ret\n",
    "            else:\n",
    "                for i in m1[cur_pos]:\n",
    "                    ret, cnt1 = get_ans(idx + 1, i)\n",
    "                    if cnt1 >= anscnt:\n",
    "                        anscnt = cnt1\n",
    "                        ans = [cur_pos] + ret\n",
    "            return ans, anscnt\n",
    "\n",
    "        ans = -1\n",
    "        rett = []\n",
    "        for i in range(n):\n",
    "            v1, ans1 = get_ans(0, i)\n",
    "            if ans1 > ans:\n",
    "                ans = ans1\n",
    "                rett = v1\n",
    "        return rett\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.mostSimilar(n=4, roads=[[1, 0], [2, 0], [3, 0], [2, 1], [3, 1], [3, 2]]\n",
    "                    , names=[\"ATL\", \"PEK\", \"LAX\", \"DXB\"],\n",
    "                    targetPath=[\"ABC\", \"DEF\"]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in roads:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        for i in range(n):\n",
    "            graph[-1].append(i)\n",
    "        @lru_cache(None)\n",
    "        def dfs(index, node):\n",
    "            if index == len(targetPath):\n",
    "                return 0, []\n",
    "            curMin = float('inf')\n",
    "            curPath = []\n",
    "            for nei in graph[node]:\n",
    "                nxt = dfs(index + 1, nei)\n",
    "                if curMin > nxt[0] + (names[nei] != targetPath[index]):\n",
    "                    curMin = nxt[0] + (names[nei] != targetPath[index])\n",
    "                    curPath = [nei] + nxt[1]\n",
    "            return curMin, curPath\n",
    "        return dfs(0, - 1)[1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, j in roads:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            res = math.inf\n",
    "            ans = []\n",
    "            if i == 0:\n",
    "                for j in range(n):\n",
    "                    cost = int(targetPath[i] != names[j])\n",
    "                    if len(targetPath) == 1:\n",
    "                        sub, sub_ans = 0, []\n",
    "                    else:\n",
    "                        sub, sub_ans = dfs(i + 1, j)\n",
    "                    if sub + cost < res:\n",
    "                        res = sub + cost\n",
    "                        ans = [j] + sub_ans\n",
    "            else:\n",
    "                for k in g[j]:\n",
    "                    cost = int(targetPath[i] != names[k])\n",
    "                    if i == len(targetPath) - 1:\n",
    "                        if cost < res:\n",
    "                            res = cost\n",
    "                            ans = [k]\n",
    "                    else:\n",
    "                        sub, sub_ans = dfs(i + 1, k)\n",
    "                        if cost + sub < res:\n",
    "                            res = cost + sub\n",
    "                            ans = [k] + sub_ans\n",
    "            return res, ans\n",
    "        return dfs(0, -1)[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:\n",
    "        d=defaultdict(list)\n",
    "        for a,b in roads:\n",
    "            d[a].append(b)\n",
    "            d[b].append(a)\n",
    "            \n",
    "        @functools.lru_cache(None)\n",
    "        def dp(roadIdx,targetIdx):\n",
    "            if targetIdx>=len(targetPath): return 0,[]\n",
    "            mincost,minpath=min([dp(nxt,targetIdx+1) for nxt in d[roadIdx]],key=lambda x:x[0])\n",
    "            return mincost+(names[roadIdx]!=targetPath[targetIdx]),[roadIdx]+minpath\n",
    "            \n",
    "        return min([dp(i,0) for i in range(n)],key=lambda x:x[0])[1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
